//leetcode 463
/*
!!!!!!!!!!!!!!!!!!!!!!!
对于一个陆地格子的每条边，它被算作岛屿的周长当且仅当这条边为网格的边界或者相邻的另一个格子为水域。
0代表水域，1代表陆地
*/
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
	int dx[4]={0,1,0,-1};
	int dy[4]={1,0,-1,0}; 
	int dfs(int x,int y,vector<vector<int>>& grid,int n,int m){
        //当第一次进入dfs时，其实并没有走这个if条件，这个if是给grid[x][y]的四个周围用的
        //其实判断的是tx和ty是否<0，当x或y是边界时，那么tx或ty一定会<0或>=m，这里也判断的是gird[tx][ty]==0(tx,ty是否是水域)
		if(x<0 || x>=n || y<0 || y>=m || grid[x][y]==0){
            // if(x<0 || x>=n || y<0 || y>=m || grid[x][y]==0)
            // 把 x>=n 改成 x==n 也可以，因为格子的边界时(n-1,m-1),那么tx和ty的最大值就是n和m,不会出现tx>n和ty>m的情况
            //但是把>=改成==以后，运行时长会增加  96s --> 124s
			return 1;
		}
		if(grid[x][y]==2){  
			return 0;
		}
		grid[x][y]=2;//当这个格子走过以后，记作2
		int res=0;//res记录该岛屿的四周共有多少条边长应该被计算到岛屿周长中
		for(int i=0;i<4;i++){
			int tx=x+dx[i];
			int ty=y+dy[i];
			res+=dfs(tx,ty,grid,n,m);
		}
		return res;
	}
	
    int islandPerimeter(vector<vector<int>>& grid) {
        int n=grid.size(),m=grid[0].size();
        int ans=0;//ans用来记录该岛屿的周长
        for(int i=0;i<n;i++){
        	for(int j=0;j<m;j++){
        		if(grid[i][j]==1){
        			ans+=dfs(i,j,grid,n,m);
				}
			}
		}
		return ans;
    }
};

/*
另一种写法：把dfs函数写在主函数中，这样更能看出来dfs中的第一个if是用来判断tx和ty的
*/
int islandPerimeter(vector<vector<int>>& grid) {
        // 下个格子的x轴与y轴加的值，右下左上
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        // n表示高度，m表示宽度
        int n = grid.size(), m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    for (int k = 0; k < 4; k++) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        // tx < 0，已是左边界；tx >= n，已是右边界
                        // ty < 0，已是上边界；ty >= m，已是下边界
                        // grid[tx][ty] == 0，相邻格子是水域
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            cnt += 1;
                        }
                    }
                    ans += cnt;
                }
            }
        }
        return ans;
}